package luoguOJ;

import java.util.Arrays;
import java.util.Scanner;

public class MainNOIP2006_Two {
    public static int max(int a, int b, int c) {
        return 0;
    }

    public static void main(String[] args) {
        int n, m, v, p, q;

        int maxn = 40000;
        int[][] f = new int[70][maxn];
        int[][] value = new int[70][3];
        int[][] imp = new int[70][3];

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt()/10;
        m = sc.nextInt();
        for (int i = 1; i <= m; i++) {
            v = sc.nextInt()/10;
            p = sc.nextInt();
            q = sc.nextInt();
            // 为主件
            if (q == 0) {
                value[i][0] = v;
                imp[i][0] = p;
            }
            // 为附件
            else {
                if (value[q][1] == 0) {
                    value[q][1] = v;
                    imp[q][1] = p;
                } else {
                    value[q][2] = v;
                    imp[q][2] = p;
                }
            }

        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (j - value[i][0] >= 0) {
                    // 仅主件
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - value[i][0]] + value[i][0] * imp[i][0]);
                    // 这个时候的f[i][j]表示仅有主件的时候的情况，而下面每种加附件的情况，都是在有主件的基础下，所以
                    // 直接和f[i][j]比较
                    // 主件 + 附件1
                    if (j - value[i][0] - value[i][1] >= 0)
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - value[i][0] - value[i][1]] + value[i][0] * imp[i][0]
                                + value[i][1] * imp[i][1]);
                    // 主件 + 附件2
                    if (j - value[i][0] - value[i][2] >= 0)
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - value[i][0] - value[i][2]] + value[i][0] * imp[i][0]
                                + value[i][2] * imp[i][2]);
                    // 主件 + 所有附件
                    if (j - value[i][0] - value[i][1] - value[i][2] >= 0)
                        f[i][j] = Math.max(f[i][j], f[i - 1][j - value[i][0] - value[i][1] - value[i][2]]
                                + value[i][0] * imp[i][0] + value[i][1] * imp[i][1] + value[i][2] * imp[i][2]);
                } else
                    f[i][j] = f[i - 1][j];
            }
        }
        for (int i = 0; i <= m; i++) {
            System.out.println(Arrays.toString(f[i]));
        }
        System.out.println(f[m][n]*10);
    }

}
